#include <bits/stdc++.h>
using namespace std;

/*
1262. 可被三整除的最大和
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个整数数组 nums，请你找出并返回能被三整除的元素 最大和。

 

示例 1：

输入：nums = [3,6,5,1,8]
输出：18
解释：选出数字 3, 6, 1 和 8，它们的和是 18（可被 3 整除的最大和）。
示例 2：

输入：nums = [4]
输出：0
解释：4 不能被 3 整除，所以无法选出数字，返回 0。
示例 3：

输入：nums = [1,2,3,4,4]
输出：12
解释：选出数字 1, 3, 4 以及 4，它们的和是 12（可被 3 整除的最大和）。
 

提示：

1 <= nums.length <= 4 * 104
1 <= nums[i] <= 104
*/

// 法一
class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        // dp
        vector<int> dp = {0, INT_MIN, INT_MIN};
        for (int num : nums) {
            vector<int> tmp = dp;
            for (int i = 0;i < 3; i++) {
                // last status can arrive
                if (tmp[i] != INT_MIN) {
                    int next = (i + num) % 3;
                    dp[next] = max(dp[next], tmp[i] + num); // update max
                }   
            }
        }
        return dp[0] == INT_MIN ? 0 : dp[0];
    }
};

// 法二
class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        int s = accumulate(nums.begin(), nums.end(), 0); // 计算数组总和
        if (s % 3 == 0) return s; // 总和已能被3整除，直接返回
        vector<int> a[3]; // 按模3余数分组：a[0]余0，a[1]余1，a[2]余2
        for (int x : nums) a[x % 3].push_back(x);
        // 排序是为了快速获取最小的1个/2个元素（减去最小元素，总和减少最少）
        sort(a[1].begin(), a[1].end());
        sort(a[2].begin(), a[2].end());
        // 核心：将「s%3=2」转化为「s%3=1」处理，统一逻辑
        // 因为s%3=2时，需要减1个余2的数 或 2个余1的数，和s%3=1的处理逻辑对称
        if (s % 3 == 2) swap(a[1], a[2]);
        // 情况1：减去1个余1的最小数（若存在）
        int ans = a[1].size() ? s - a[1][0] : 0;
        // 情况2：减去2个余2的最小数（若至少有2个），取两种情况的最大值
        if (a[2].size() > 1) ans = max(ans, s - a[2][0] - a[2][1]);
        return ans;
    }
};